#include <iostream>
#include <vector>
using namespace std;
namespace bit
{
    template<class T>
    struct HashBucketNode
    {
        T _data;
        HashBucketNode* _pNext;

        HashBucketNode(const T& data)
            : _data(data), _pNext(nullptr)
        {}
    };
    template<class K>
    struct DefHashF
    {
        size_t operator()(const K& key) const
        {
            return std::hash<K>()(key);
        }
    };

	// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
	template<class K, class V, class KeyOfValue, class HF>
	class HashBucket;
    
	// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
	template <class K, class V, class KeyOfValue, class HF>
	struct HBIterator
	{
		typedef HashBucket<K, V, KeyOfValue, HF> HashBucket;
		typedef HashBucketNode<V>* PNode;
		typedef HBIterator<K, V, KeyOfValue, HF> Self;

		HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr): _pNode(pNode), _pHt(pHt) {}
		Self& operator++()
		{
			// 当前迭代器所指节点后还有节点时直接取其下一个节点
			if (_pNode->_pNext)
				_pNode = _pNode->_pNext;
			else
			{
				// 找下一个不空的桶，返回该桶中第一个节点
				size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data)) + 1;
				for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
				{
					if (_pHt->_ht[bucketNo]){
                        _pNode = _pHt->_ht[bucketNo];
                        break;
                    }
				}
                if (bucketNo >= _pHt->BucketCount()) _pNode = nullptr;
			}

			return *this;
		}
        Self operator++(int) {
            Self tmp = *this;
            ++(*this);
            return tmp;
        }

        V &operator*() { return _pNode->_data; }
        V *operator->() { return &(_pNode->_data); }

        bool operator==(const Self &it) const {
            return _pNode == it._pNode;
        }
        bool operator!=(const Self &it) const {
            return _pNode != it._pNode;
        }
        PNode _pNode;             // 当前迭代器关联的节点
		HashBucket* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
	};
    template<class K, class V, class KeyOfValue, class HF = DefHashF<K>>
    class HashBucket
    {
        typedef HashBucketNode<V> Node;
    public:
        typedef HBIterator<K, V, KeyOfValue, HF> Iterator;

        HashBucket()
            : _ht(10, nullptr), _size(0)
        {}

        ~HashBucket()
        {
            Clear();
        }

        void Clear()
        {
            for (auto& p : _ht)
            {
                Node* cur = p;
                while (cur)
                {
                    Node* next = cur->_pNext;
                    delete cur;
                    cur = next;
                }
                p = nullptr;
            }
        }

        size_t HashFunc(const K& key) const
        {
            HF hf;
            return hf(key) % _ht.size();
        }

        pair<Iterator, bool> Insert(const V& value)
        {
            if (LoadFactor() >= 1.0)
                Rehash();

            size_t bucketNo = HashFunc(KeyOfValue()(value));
            Node* cur = _ht[bucketNo];
            while (cur)
            {
                if (cur->_data == value)
                    return make_pair(Iterator(cur, this), false);
                cur = cur->_pNext;
            }
            Node* newNode = new Node(value);
            newNode->_pNext = _ht[bucketNo];
            _ht[bucketNo] = newNode;
            ++_size;
            return make_pair(Iterator(newNode, this), true);
        }

        Iterator Find(const K& key)
        {
            size_t bucketNo = HashFunc(key);
            Node* cur = _ht[bucketNo];
            while (cur)
            {
                if (KeyOfValue()(cur->_data) == key)
                    return Iterator(cur, this);
                cur = cur->_pNext;
            }
            return end();
        }

        size_t Count(const K& key)
        {
            return Find(key) != end();
        }

        Iterator Erase(Iterator pos)
        {
            if (pos._pNode == nullptr) return pos;

            size_t bucketNo = HashFunc(KeyOfValue()(pos._pNode->_data));
            Node*& head = _ht[bucketNo];

            if (head == pos._pNode)
            {
                head = head->_pNext;
                delete pos._pNode;
                --_size;
                return Iterator(head, this);
            }
            Node* prev = head;
            while (prev && prev->_pNext != pos._pNode)
                prev = prev->_pNext;

            if (prev)
            {
                prev->_pNext = pos._pNode->_pNext;
                Node* next = pos._pNode->_pNext;
                delete pos._pNode;
                --_size;
                return Iterator(next, this);
            }
            return end();
        }

        Iterator begin()
        {
            for (size_t i = 0; i < _ht.size(); ++i)
            {
                if (_ht[i]) return Iterator(_ht[i], this);
            }
            return end();
        }

        Iterator end()
        {
            return Iterator(nullptr, this);
        }

        size_t BucketCount() const { return _ht.size(); }
        size_t size() const { return _size; }
        bool empty() const { return _size == 0; }

        size_t BucketSize(const K& key)
        {
            size_t bucketNo = HashFunc(key);
            Node* cur = _ht[bucketNo];
            size_t cnt = 0;
            while (cur)
            {
                ++cnt;
                cur = cur->_pNext;
            }
            return cnt;
        }

        double LoadFactor() const
        {
            return (double)_size / _ht.size();
        }

        void Rehash()
        {
            vector<Node*> newTable(_ht.size() * 2, nullptr);
            for (auto p : _ht)
            {
                while (p)
                {
                    Node* next = p->_pNext;
                    size_t bucketNo = HF()(KeyOfValue()(p->_data)) % newTable.size();
                    p->_pNext = newTable[bucketNo];
                    newTable[bucketNo] = p;
                    p = next;
                }
            }
            _ht.swap(newTable);
        }

        vector<Node*> _ht;
        size_t _size;
    };
	// unordered_set中存储的是K类型，HF哈希函数类型
	// unordered_set在实现时，只需将hashbucket中的接口重新封装即可
    template<class K>
    struct SetKeyOfValue
    {
        const K& operator()(const K& data) const
        {
            return data;
        }
    };
	template<class K, class HF = DefHashF<K>>
	class unordered_set
	{
		// 通过key获取value的操作
        typedef HashBucket<K, K, SetKeyOfValue<K>, HF> HT;
	public:
		typedef typename HT::Iterator iterator; // 取出定义的Iterator类型
	public:
		unordered_set() : _ht()
		{}
		////////////////////////////////////////////////////
		iterator begin(){ return _ht.begin(); }
		iterator end(){ return _ht.end(); }
		////////////////////////////////////////////////////////////
		// capacity
		size_t size()const{ return _ht.size(); }
		bool empty()const{ return _ht.empty(); }
		///////////////////////////////////////////////////////////
		// lookup
		iterator find(const K& key){ return _ht.Find(key); }
		size_t count(const K& key){ return _ht.Count(key); }
		/////////////////////////////////////////////////
		// modify
		pair<iterator, bool> insert(const K& valye)
		{
			return _ht.Insert(valye);
		}

		iterator erase(iterator position)
		{
			return _ht.Erase(position);
		}
		////////////////////////////////////////////////////////////
		// bucket
		size_t bucket_count(){ return _ht.BucketCount(); }
		size_t bucket_size(const K& key){ return _ht.BucketSize(key); }
	private:
		HT _ht;
	};
}
using namespace bit;
int main()
{
    bit::unordered_set<int> us;
    us.insert(10);
    us.insert(20);
    us.insert(30);

    for (auto x : us)
        cout << x << " ";
    cout << endl;

    return 0;
}

